{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #All Ancestors of a Node in a Directed Acyclic Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getAncestors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有向无环图中一个节点的所有祖先"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp;<code>n</code>&nbsp;，它表示一个 <strong>有向无环图</strong>&nbsp;中节点的数目，节点编号为&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;（包括两者）。</p>\n",
    "\n",
    "<p>给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [from<sub>i</sub>, to<sub>i</sub>]</code>&nbsp;表示图中一条从&nbsp;<code>from<sub>i</sub></code>&nbsp;到&nbsp;<code>to<sub>i</sub></code>&nbsp;的单向边。</p>\n",
    "\n",
    "<p>请你返回一个数组&nbsp;<code>answer</code>，其中<em>&nbsp;</em><code>answer[i]</code>是第&nbsp;<code>i</code>&nbsp;个节点的所有&nbsp;<strong>祖先</strong>&nbsp;，这些祖先节点&nbsp;<strong>升序</strong>&nbsp;排序。</p>\n",
    "\n",
    "<p>如果 <code>u</code>&nbsp;通过一系列边，能够到达 <code>v</code>&nbsp;，那么我们称节点 <code>u</code>&nbsp;是节点 <code>v</code>&nbsp;的 <strong>祖先</strong>&nbsp;节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/12/12/e1.png\" style=\"width: 322px; height: 265px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]\n",
    "<b>输出：</b>[[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1,2,3]]\n",
    "<strong>解释：</strong>\n",
    "上图为输入所对应的图。\n",
    "- 节点 0 ，1 和 2 没有任何祖先。\n",
    "- 节点 3 有 2 个祖先 0 和 1 。\n",
    "- 节点 4 有 2 个祖先 0 和 2 。\n",
    "- 节点 5 有 3 个祖先 0 ，1 和 3 。\n",
    "- 节点 6 有 5 个祖先 0 ，1 ，2 ，3 和 4 。\n",
    "- 节点 7 有 4 个祖先 0 ，1 ，2 和 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/12/12/e2.png\" style=\"width: 343px; height: 299px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]\n",
    "<b>输出：</b>[[],[0],[0,1],[0,1,2],[0,1,2,3]]\n",
    "<strong>解释：</strong>\n",
    "上图为输入所对应的图。\n",
    "- 节点 0 没有任何祖先。\n",
    "- 节点 1 有 1 个祖先 0 。\n",
    "- 节点 2 有 2 个祖先 0 和 1 。\n",
    "- 节点 3 有 3 个祖先 0 ，1 和 2 。\n",
    "- 节点 4 有 4 个祖先 0 ，1 ，2 和 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= edges.length &lt;= min(2000, n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>\n",
    "\t<li>图中不会有重边。</li>\n",
    "\t<li>图是 <strong>有向</strong> 且 <strong>无环</strong> 的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [all-ancestors-of-a-node-in-a-directed-acyclic-graph](https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [all-ancestors-of-a-node-in-a-directed-acyclic-graph](https://leetcode.cn/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['8\\n[[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3,6],[3,7],[4,6]]', '5\\n[[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        G = defaultdict(list)\n",
    "        revG = defaultdict(list)\n",
    "        o = [0] * n\n",
    "        q = []\n",
    "        for a,b in edges:\n",
    "            G[a].append(b)\n",
    "            revG[b].append(a)\n",
    "            o[b] += 1\n",
    "        for idx,v in enumerate(o):\n",
    "            heappush(q,(v,idx))\n",
    "        Res = [None] * n\n",
    "        vis = [0] * n\n",
    "        while q:\n",
    "            _,out = heappop(q)\n",
    "            if vis[out]:continue\n",
    "            vis[out] = 1\n",
    "            S = set()\n",
    "            for i in revG[out]:\n",
    "                S.add(i)\n",
    "                for x in Res[i]:S.add(x)\n",
    "            Res[out] = sorted(list(S))\n",
    "            for i in G[out]:\n",
    "                o[i] -= 1\n",
    "                heappush(q,(o[i],i))\n",
    "        return Res\n",
    "            \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "def record_parent(parent_record: set, node, paths):\n",
    "    if node in paths:\n",
    "        for parent_node in paths[node]:\n",
    "            if parent_node not in parent_record:\n",
    "                parent_record.add(parent_node)\n",
    "                record_parent(parent_record, parent_node, paths)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        paths = {}\n",
    "        # 计算所有反向路径\n",
    "        for edge in edges:\n",
    "            if edge[1] not in paths:\n",
    "                paths[edge[1]] = set()\n",
    "            paths[edge[1]].add(edge[0])\n",
    "\n",
    "        parent_records = []\n",
    "        for i in range(n):\n",
    "            parent_record = set()\n",
    "            record_parent(parent_record, i, paths)\n",
    "            parent_record = sorted(list(parent_record))\n",
    "            parent_records.append(parent_record)\n",
    "\n",
    "        return parent_records\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def find(num,node,res):\n",
    "    res_i = []\n",
    "    for i in node[num]:\n",
    "        if i not in res_i:\n",
    "            res_i.append(i)\n",
    "        if i not in res.keys():\n",
    "            find(i,node,res)\n",
    "        for i in res[i]:\n",
    "            if i not in res_i:\n",
    "                res_i.append(i)\n",
    "    res_i.sort()\n",
    "    res[num] = res_i\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        outdu = {}\n",
    "        indu = {}\n",
    "        node = {}\n",
    "        res = {}\n",
    "        for i in range(n):\n",
    "            outdu[i] = 0\n",
    "            indu[i] = 0\n",
    "            node[i] = []\n",
    "        for i in range(len(edges)):\n",
    "            fromi = edges[i][0]\n",
    "            toi = edges[i][1]\n",
    "            outdu[fromi]+=1\n",
    "            indu[toi]+=1\n",
    "            node[toi].append(fromi)\n",
    "\n",
    "        res = {}\n",
    "        for i in range(n):\n",
    "            if i not in res.keys():\n",
    "                find(i,node,res)\n",
    "        res_list = []\n",
    "        for i in range(n):\n",
    "            res_list.append(res[i])\n",
    "        return res_list\n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        BFS 遍历每一个节点，通过bfs遍历该节点的每一个子节点，将该节点是父节点的信息记录下来\n",
    "        \"\"\"\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "        \n",
    "        ans = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            q = deque(g[i])\n",
    "            seen = set(g[i])\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                ans[u].append(i)\n",
    "                for v in g[u]:\n",
    "                    if v not in seen:\n",
    "                        seen.add(v)\n",
    "                        q.append(v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        drgee = [0] * n \r\n",
    "        for f, t in edges:\r\n",
    "            g[f].append(t)\r\n",
    "            drgee[t] += 1 \r\n",
    "        q = [x for x in range(n) if drgee[x] == 0]\r\n",
    "        res = [[] for _ in range(n)]\r\n",
    "        while q:\r\n",
    "            tmp = q \r\n",
    "            q = []\r\n",
    "            for x in tmp:\r\n",
    "                for y in g[x]:\r\n",
    "                    drgee[y] -= 1\r\n",
    "                    fs = []\r\n",
    "                    for f in res[x] + [x]:\r\n",
    "                        j = bisect_left(res[y], f)\r\n",
    "                        if j == len(res[y]) or res[y][j] != f:\r\n",
    "                            fs.append(f)\r\n",
    "                    res[y].extend(fs)\r\n",
    "                    res[y].sort()\r\n",
    "                    if drgee[y] == 0:\r\n",
    "                        q.append(y)  \r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        fat=defaultdict(list)\n",
    "        for x,y in edges:\n",
    "            fat[y].append(x)\n",
    "        ans=[]\n",
    "        for i in range (0,n):\n",
    "            queue=[i]\n",
    "            visited=[0]*n\n",
    "            visited[i]=1\n",
    "            tem=[]\n",
    "            while queue:\n",
    "                m=len(queue)\n",
    "                for _ in range (0,m):\n",
    "                    x=queue.pop(0)\n",
    "                    for adj in fat[x]:\n",
    "                        if visited[adj]==0:\n",
    "                            visited[adj]=1\n",
    "                            queue.append(adj)\n",
    "                            tem.append(adj)\n",
    "            tem.sort()\n",
    "            ans.append(tem)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        indegrees = defaultdict(int)\n",
    "        nxt_map = defaultdict(set)\n",
    "        for f, t in edges:\n",
    "            indegrees[t] += 1\n",
    "            nxt_map[f].add(t) \n",
    "        \n",
    "        stack = [i for i in range(n) if indegrees[i] == 0]\n",
    "        ans = [[] for i in range(n)]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            for nxt in nxt_map[node]:\n",
    "                ans[nxt].append(node)\n",
    "                ans[nxt].extend(ans[node])\n",
    "                indegrees[nxt] -= 1\n",
    "                if indegrees[nxt] == 0:\n",
    "                    ans[nxt] = sorted(set(ans[nxt]))\n",
    "                    stack.append(nxt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self, id):\n",
    "        self.par = []\n",
    "        self.id = id\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def getallpar(self, node):\n",
    "        output = node.par[:]\n",
    "        for i in node.par:\n",
    "            if self.output[i] != None:\n",
    "                output.extend(self.output[i])\n",
    "            else:\n",
    "                output.extend(self.getallpar(self.node_lst[i]))\n",
    "        \n",
    "        t = list(set(output))\n",
    "        t.sort()\n",
    "        self.output[node.id] = t\n",
    "\n",
    "        return t\n",
    "\n",
    "\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        node_lst = []\n",
    "        self.node_lst = node_lst\n",
    "        for i in range(n):\n",
    "            node_lst.append(node(i))\n",
    "        \n",
    "        for edge in edges:\n",
    "            par, i = edge\n",
    "            node_lst[i].par.append(par)\n",
    "        \n",
    "        self.output = [None for i in range(n)]\n",
    "        \n",
    "        for i, v in enumerate(self.output):\n",
    "            if self.output[i] != None:\n",
    "                pass\n",
    "            else:\n",
    "                self.getallpar(node_lst[i])\n",
    "\n",
    "        return self.output\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        mask = [0] * n\n",
    "        # 建图\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[y].append(x)  # frm x to y\n",
    "        \n",
    "        # 遍历并维护节点\n",
    "        def dfs(i):\n",
    "            res = []\n",
    "            for j in graph[i]:\n",
    "                res.append(j)\n",
    "                if mask[j]==0:\n",
    "                    ans[j] = sorted(list(set(dfs(j))))\n",
    "                    mask[j] = 1\n",
    "                res.extend(ans[j])\n",
    "            return res\n",
    "\n",
    "        ans = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if mask[i] == 0:\n",
    "                ans[i] = sorted(list(set(dfs(i))))\n",
    "                mask[i] = 1\n",
    "        \n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        tree = [[] for _ in range(n)]\n",
    "        deg = defaultdict(int)\n",
    "        for e in edges:\n",
    "            tree[e[0]].append(e[1])\n",
    "            deg[e[1]] += 1\n",
    "        que = []\n",
    "        for k in range(n):\n",
    "            if deg[k] == 0:\n",
    "                que.append(k)\n",
    "        ans = [[] for _ in range(n)]\n",
    "        while que:\n",
    "            cur = que.pop()\n",
    "            ans[cur] = sorted(list(set(ans[cur])))\n",
    "            for nxt in tree[cur]:\n",
    "                ans[nxt].append(cur)\n",
    "                ans[nxt] += ans[cur]\n",
    "                deg[nxt] -= 1\n",
    "                if deg[nxt] == 0:\n",
    "                    que.append(nxt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        def dfs(i: int, s: int):\n",
    "            for j in g[i]:\n",
    "                if j not in vis:\n",
    "                    vis.add(j)\n",
    "                    ans[j].append(s)\n",
    "                    dfs(j, s)\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "        ans = [[] for _ in range(n)]\n",
    "        vis = set()\n",
    "        for i in range(n):\n",
    "            dfs(i, i)\n",
    "            vis.clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        graph = defaultdict(list)\n",
    "        for f,t in edges:\n",
    "            graph[f].append(t)\n",
    "        \n",
    "        answer = [[] for _ in range(n)]\n",
    "        def dfs(start, node, met):\n",
    "            # if len(graph)==0: return\n",
    "            for nextN in graph[node]:\n",
    "                if met[nextN]==False:\n",
    "                    answer[nextN].append(start)\n",
    "                    met[nextN] = True\n",
    "                    dfs(start, nextN, met)\n",
    "\n",
    "        for i in range(n):\n",
    "            cmet = [False]*n\n",
    "            dfs(i,i, cmet)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        g=collections.defaultdict(list)\n",
    "        start,end=set(),set()\n",
    "        ans=[[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[v].append(u) \n",
    "            start.add(u)\n",
    "            end.add(v)\n",
    "        current=list(end-start)\n",
    "        #print(current)\n",
    "        def dfs(u):\n",
    "            nonlocal ans\n",
    "            if ans[u]:\n",
    "                return ans[u]\n",
    "            \n",
    "            current=set()\n",
    "            for v in g[u]:\n",
    "                current.update(dfs(v))\n",
    "                current.add(v)\n",
    "                #print(v,current)\n",
    "            #print(u,current)\n",
    "            ans[u]=sorted(list(current))\n",
    "            return current\n",
    "\n",
    "        for curr in current:\n",
    "            dfs(curr)\n",
    "\n",
    "        \n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        t={}\n",
    "        for e in edges:\n",
    "            if e[1] in t:t[e[1]]+=[e[0]]\n",
    "            else:t[e[1]]=[e[0]]\n",
    "        @lru_cache()\n",
    "        def dfs(i):return list(set(x for p in t[i] for x in [p]+dfs(p))) if i in t else []\n",
    "        return [sorted(dfs(i)) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        dp = []\n",
    "        [dp.append([]) for _ in range(n)]\n",
    "        while True:\n",
    "            list1 = dp[:]\n",
    "            for temp in edges:\n",
    "                l1 = dp[temp[0]] + [temp[0]] + dp[temp[1]]\n",
    "                l2 = list(set(l1))\n",
    "                l2.sort()\n",
    "                dp[temp[1]] = l2\n",
    "            if list1 == dp:\n",
    "                break\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[] for i in range(n)]\n",
    "        visited = [[False] * n for i in range(n)] # ans is in res\n",
    "\n",
    "        for s, t in edges:\n",
    "            res[t].append(s)\n",
    "            visited[t][s] = True\n",
    "        \n",
    "        for i in range(n):\n",
    "            queue = res[i].copy()\n",
    "            # all element in queue is the ans of i\n",
    "            while queue:\n",
    "                l = len(queue)\n",
    "                for j in range(l):\n",
    "                    ch = queue[j]\n",
    "                    for ans in res[ch]:\n",
    "                        if not visited[i][ans]:\n",
    "                            queue.append(ans)\n",
    "                            visited[i][ans] = True\n",
    "                        # if not visited[ch][ans]:\n",
    "                        #     res[ch].append(ans)\n",
    "                        #     visited[ch][ans] = True\n",
    "                queue = queue[l:]\n",
    "                res[i] += queue\n",
    "        \n",
    "        return [sorted(r) for r in res]\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        graph=defaultdict(list)\n",
    "        for e in edges:\n",
    "            graph[e[1]].append(e[0])\n",
    "        ans=[[] for i in range(n)]\n",
    "\n",
    "        def dfs(x,i):\n",
    "            for v in graph[x]:\n",
    "                if not visited[v]:\n",
    "                    visited[v]=True\n",
    "                    ans[i].append(v)\n",
    "                    dfs(v,i)\n",
    "        \n",
    "        for i in range(n):\n",
    "            visited=[False for i in range(n)]\n",
    "            dfs(i,i)\n",
    "\n",
    "\n",
    "        return [sorted(a) for a in ans]\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        dct = defaultdict(list)\n",
    "        for i, j in edges:\n",
    "            dct[j].append(i)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x):\n",
    "            res = []\n",
    "            for i in dct[x]:\n",
    "                res.append(i)\n",
    "                res.extend(dfs(i))\n",
    "            return list(set(res))\n",
    "        \n",
    "        return [sorted(dfs(i)) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        # DFS\n",
    "        memo_anc = [[] for _ in range(n)]\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for c in edges:\n",
    "            graph[c[1]].append(c[0])\n",
    "        res = [[] for _ in range(n)]\n",
    "        def findanc(p):\n",
    "            if memo_anc[p]:\n",
    "                return memo_anc[p]\n",
    "            ans = []\n",
    "            for c in graph[p]:\n",
    "                if c not in ans:\n",
    "                    ans.append(c)\n",
    "                curanc = findanc(c)\n",
    "                for i in curanc:\n",
    "                    if i not in ans:\n",
    "                        ans.append(i)        \n",
    "            memo_anc[p] = ans\n",
    "            return ans\n",
    "        \n",
    "        for i in range(n):\n",
    "            res[i] = list(sorted(findanc(i)))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self, id):\n",
    "        self.par = []\n",
    "        self.id = id\n",
    "        self.all_par = None\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def getallpar(self, node):\n",
    "        node.all_par = node.par[:]\n",
    "        for i in node.par:\n",
    "            if i.all_par != None:\n",
    "                pass\n",
    "            else:\n",
    "                self.getallpar(i)\n",
    "            node.all_par.extend(i.all_par)\n",
    "        node.all_par = list(set(node.all_par))\n",
    "        # print(node.all_par)\n",
    "        # return node.all_par\n",
    "\n",
    "\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        node_lst = []\n",
    "        self.node_lst = node_lst\n",
    "        for i in range(n):\n",
    "            node_lst.append(node(i))\n",
    "        \n",
    "        for edge in edges:\n",
    "            par, i = edge\n",
    "            node_lst[i].par.append(node_lst[par])\n",
    "        \n",
    "        # self.output = [None for i in range(n)]\n",
    "        output = []\n",
    "        for i, v in enumerate(node_lst):\n",
    "            if v.all_par != None:\n",
    "                pass\n",
    "            else:\n",
    "                self.getallpar(node_lst[i])\n",
    "            t = [i.id for i in v.all_par]\n",
    "            t.sort()\n",
    "            output.append(t)\n",
    "\n",
    "        return output\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        res = {}\n",
    "        for i in range(n):\n",
    "            res[i] = []\n",
    "        ends = list(range(n))\n",
    "        for e in edges:\n",
    "            res[e[1]].append(e[0])\n",
    "            if e[0] in ends:\n",
    "                ends.remove(e[0])\n",
    "        back_c = {}\n",
    "        import functools\n",
    "        @functools.lru_cache()\n",
    "        def back(e):\n",
    "            for e_i in range(len(res[e])):\n",
    "                if back_c.get(res[e][e_i]) is None:\n",
    "                    b_cache = back(res[e][e_i])\n",
    "                    res[e] += b_cache\n",
    "                    back_c[res[e][e_i]] = b_cache\n",
    "                else:\n",
    "                    res[e] += back_c.get(res[e][e_i])\n",
    "            res[e] = list(set(res[e]))\n",
    "            return res[e]\n",
    "        for e in ends:\n",
    "            if back_c.get(e) is None:\n",
    "                b_e = back(e)\n",
    "                back_c[e] = b_e\n",
    "\n",
    "        values = list(res.values())\n",
    "        values = [sorted(v)  for v in values]\n",
    "        return values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        fdic = {i:[] for i in range(n)}\n",
    "        tdic = {i:[] for i in range(n)}\n",
    "        self.res = [[] for _ in range(n)]\n",
    "        for (f, t) in edges:\n",
    "            fdic[f].append(t)\n",
    "            tdic[t].append(f)\n",
    "        first = [t for t in tdic if not tdic[t]]\n",
    "        def recur(p):\n",
    "            if not p:\n",
    "                return\n",
    "            nex = []\n",
    "            for f in p:\n",
    "                nex += fdic[f]\n",
    "                for t in fdic[f]:\n",
    "                    self.res[t].append(f)\n",
    "                    self.res[t] += self.res[f]\n",
    "                    self.res[t] = list(set(self.res[t]))\n",
    "            # print(self.res)\n",
    "            nex = list(set(nex))\n",
    "            recur(nex)\n",
    "        recur(first)\n",
    "        return [sorted(list(set(r))) for r in self.res]\n",
    "        \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.father = defaultdict(list)\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        #首先记录以下某个某个点能到达哪里\n",
    "        arrive = defaultdict(list)\n",
    "        \n",
    "\n",
    "        for s,e in edges:\n",
    "            arrive[s].append(e)\n",
    "            self.father[e].append(s)\n",
    "\n",
    "        \n",
    "        answer = [[] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            answer[i]= self.dfs(i)\n",
    "           \n",
    "        return answer\n",
    "    \n",
    "\n",
    "    @lru_cache(None)\n",
    "    def dfs(self, node):\n",
    "        if not self.father[node]:\n",
    "            return []\n",
    "            \n",
    "        ans = []\n",
    "        for f in self.father[node]:\n",
    "            pre = self.dfs(f)\n",
    "            ans.append(f)\n",
    "            ans.extend(pre)\n",
    "            ans = sorted(list(set(ans)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        thedict = {}\n",
    "        for i in range(len(edges)):\n",
    "            if edges[i][0] in thedict:\n",
    "                thedict[edges[i][0]].append(edges[i][1])\n",
    "            else:\n",
    "                thedict[edges[i][0]] = [edges[i][1]]\n",
    "        #print(thedict)\n",
    "        \n",
    "        sons = {}\n",
    "        def dfs(i,ancestors):           #无环图\n",
    "            if i not in thedict:\n",
    "                return\n",
    "            if i==ancestors:\n",
    "                sons[ancestors] = []\n",
    "                \n",
    "            for j in range(len(thedict[i])):\n",
    "                if thedict[i][j] not in sons[ancestors]:\n",
    "                    sons[ancestors].append(thedict[i][j])\n",
    "                    dfs(thedict[i][j],ancestors)\n",
    "            return\n",
    "        \n",
    "        for i in thedict.keys():\n",
    "            dfs(i,i)\n",
    "        #print(sons)\n",
    "        \n",
    "        res = [[] for i in range(n)]\n",
    "        for i in sons.keys():\n",
    "            for j in range(len(sons[i])):\n",
    "                res[sons[i][j]].append(i)\n",
    "        \n",
    "        for i in range(len(res)):\n",
    "            res[i].sort()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        d = [0] * n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            d[b] += 1\n",
    "            g[a].append(b)\n",
    "        ans = [set() for _ in range(n)]\n",
    "        q = deque([i for i in range(n) if d[i] == 0])\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            for a in g[t]:\n",
    "                ans[a].add(t)\n",
    "                ans[a] |= ans[t]\n",
    "                d[a] -= 1\n",
    "                if d[a] == 0:\n",
    "                    q.append(a)\n",
    "        \n",
    "        for i in range(n):\n",
    "            ans[i] = list(ans[i])\n",
    "            ans[i].sort()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        in_degree = [0] * n\n",
    "        graph = collections.defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            in_degree[v] += 1\n",
    "\n",
    "        ans = [set() for _ in range(n)]\n",
    "        q = collections.deque()\n",
    "        for i, val in enumerate(in_degree):\n",
    "            if val == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            cur_node = q.popleft()\n",
    "            for node in graph[cur_node]:\n",
    "                ans[node].add(cur_node)\n",
    "                ans[node].update(ans[cur_node])\n",
    "                in_degree[node] -= 1\n",
    "                if in_degree[node] == 0:\n",
    "                    q.append(node)\n",
    "\n",
    "        for i in range(n):\n",
    "            ans[i] = list(ans[i])\n",
    "            ans[i].sort()\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        points = set(range(0,n))\n",
    "        graph1 = {}\n",
    "        for edge in edges:\n",
    "            start, end = edge\n",
    "            graph1[end] = graph1.get(end, []) + [start]\n",
    "        starts = points - set(graph1.keys())\n",
    "        self.res = {}\n",
    "        for i in range(n):\n",
    "            self.res[i] = set([i])\n",
    "\n",
    "        graph2 = {}\n",
    "        for edge in edges:\n",
    "            start, end = edge\n",
    "            graph2[start] = graph2.get(start, []) + [end]\n",
    "        couches = self.topo_sort(starts, graph1, graph2)\n",
    "        \n",
    "        for x in graph1:\n",
    "            graph1[x] = set(graph1[x])\n",
    "        for x in graph2:\n",
    "            graph2[x] = set(graph2[x])\n",
    "        #print(graph1)\n",
    "        #print(graph2)\n",
    "        #print(couches)\n",
    "        \n",
    "        for couche in couches[1:]:\n",
    "            for item in couche:\n",
    "                parents = graph1[item]\n",
    "                for parent in parents:\n",
    "                    self.res[item] |= self.res.get(parent)\n",
    "        #print(self.res)\n",
    "        for x in self.res:\n",
    "            self.res[x] = list(self.res[x])\n",
    "            \n",
    "        self.result = [0 for x in range(n)]\n",
    "        for x,y in self.res.items():\n",
    "            y.remove(x)\n",
    "            self.result[x] = sorted(y)\n",
    "        return self.result\n",
    "            \n",
    "       \n",
    "    \n",
    "    def topo_sort(self, starts, graph1, graph2):\n",
    "        '''\n",
    "        {2: {5, 7}, 7: {8}, 3: {8}, 6: {1}, 0: {9}}\n",
    "        {5: {2}, 8: {3, 7}, 7: {2}, 1: {6}, 9: {0}}\n",
    "        \n",
    "        [1, 4, 5, 8, 9],  0:[0] 1:[1] 2:[2] 3:[3] 4:[4] 5:[5] 6:[6] 7:[7] 8:[8] 9:[9]\n",
    "          [0, 3, 6, 7], \n",
    "               [2]\n",
    "\n",
    "\n",
    "        '''\n",
    "        \n",
    "        couches = [list(starts)]\n",
    "        q = [x for x in starts]\n",
    "        passed = set(q)\n",
    "        while q:\n",
    "            couche = [x for x in q]\n",
    "            q = set()\n",
    "            for each in couche:\n",
    "                next_items = graph2.get(each,[])\n",
    "                for item in next_items:\n",
    "                    flag, parents = self.cette_couche(item, graph1, passed)\n",
    "                    if flag:\n",
    "                        q.add(item)\n",
    "                                   \n",
    "            for item in q:\n",
    "                passed.add(item)\n",
    "            if q:\n",
    "                couches.append(sorted(list(q)))\n",
    "        return couches\n",
    "                \n",
    "                \n",
    "    def cette_couche(self, item, graph1, passed):\n",
    "        parents = graph1[item]\n",
    "        return (not (set(parents) - passed), parents)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        queue = []\n",
    "        c = {}\n",
    "        in_l = [0] * n\n",
    "        res = [set() for _ in range(n)]\n",
    "        \n",
    "        for e in edges:\n",
    "            if e[0] in c:\n",
    "                c[e[0]].append(e[1])\n",
    "            else:\n",
    "                c[e[0]] = [e[1]]\n",
    "            in_l[e[1]] += 1\n",
    "        #print(c,in_l)\n",
    "        for i in range(n):\n",
    "            if in_l[i] == 0:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            x = len(queue)\n",
    "            #print(queue)\n",
    "            for i in range(x):\n",
    "                cur = queue.pop(0)\n",
    "                if cur in c:\n",
    "                    for j in c[cur]:\n",
    "                        in_l[j] -= 1\n",
    "                        res[j].add(cur)\n",
    "                        res[j].update(res[cur])\n",
    "                        if in_l[j] == 0:\n",
    "                            queue.append(j)\n",
    "        for i in range(n):\n",
    "            res[i] = sorted(list(res[i]))\n",
    "        return res\n",
    "            \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        to = defaultdict(set)\n",
    "        indegree =  [0]*n\n",
    "        for i in edges:\n",
    "            to[i[0]].add(i[1])\n",
    "            indegree[i[1]]+=1\n",
    "        res = [set()for i in range(n)]\n",
    "        queue =deque([])\n",
    "        for i in range(n):\n",
    "            if not indegree[i]:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for i in to[node]:\n",
    "                res[i].add(node)\n",
    "                res[i]|=res[node]\n",
    "                indegree[i]-=1\n",
    "                if not indegree[i]:\n",
    "                    queue.append(i)\n",
    "        for i in range(len(res)):\n",
    "            res[i] = sorted(res[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        to = defaultdict(set)\n",
    "        fr =  defaultdict(set)\n",
    "        for i in edges:\n",
    "            to[i[0]].add(i[1])\n",
    "            fr[i[1]].add(i[0])\n",
    "        res = [set()for i in range(n)]\n",
    "        queue =deque([])\n",
    "        for i in range(n):\n",
    "            if not fr[i]:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for i in to[node]:\n",
    "                res[i].add(node)\n",
    "                res[i]|=res[node]\n",
    "                fr[i].remove(node)\n",
    "                if not fr[i]:\n",
    "                    queue.append(i)\n",
    "        for i in range(len(res)):\n",
    "            res[i] = sorted(res[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        res = [set() for _ in range(n)]\n",
    "        children = [[] for _ in range(n)]\n",
    "        in_degrees = [0] * n\n",
    "        for fm, to in edges:\n",
    "            in_degrees[to] += 1\n",
    "            res[to].add(fm)\n",
    "            children[fm].append(to)\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if not in_degrees[i]:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            v = q.popleft()\n",
    "            for i in res[v]:\n",
    "                res[v] = res[v].union(res[i])\n",
    "            for c in children[v]:\n",
    "                in_degrees[c] -= 1\n",
    "                if not in_degrees[c]:\n",
    "                    q.append(c)\n",
    "        for i in range(n):\n",
    "            res[i] = sorted(list(res[i]))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        dct = dict()\n",
    "        in_degree = dict()\n",
    "        for fr, to in edges:\n",
    "            if fr not in dct:\n",
    "                dct[fr] = []\n",
    "            dct[fr].append(to)\n",
    "            in_degree[to] = in_degree.get(to, 0) + 1\n",
    "\n",
    "        stack = [i for i in range(n) if i not in in_degree]\n",
    "        ans = dict()\n",
    "        for i in range(n):\n",
    "            ans[i] = dict()\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for node in stack:\n",
    "                for to in dct.get(node, []):\n",
    "                    for fr in ans[node]:\n",
    "                        ans[to][fr] = 1\n",
    "                    ans[to][node] = 1\n",
    "                    in_degree[to] -= 1\n",
    "                    if in_degree[to] == 0:\n",
    "                        nex.append(to)\n",
    "            stack = nex[:]\n",
    "        \n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            frs = list(ans[i].keys())\n",
    "            frs.sort()\n",
    "            res.append(frs)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        res = [set() for _ in range(n)]\n",
    "        children = [[] for _ in range(n)]\n",
    "        in_degrees = [0] * n\n",
    "        for fm, to in edges:\n",
    "            in_degrees[to] += 1\n",
    "            res[to].add(fm)\n",
    "            children[fm].append(to)\n",
    "\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if not in_degrees[i]:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            v = q.popleft()\n",
    "            # for i in res[v]:\n",
    "            #     res[v] = res[v].union(res[i])\n",
    "            for c in children[v]:\n",
    "                res[c].update(res[v])\n",
    "                in_degrees[c] -= 1\n",
    "                if not in_degrees[c]:\n",
    "                    q.append(c)\n",
    "        for i in range(n):\n",
    "            res[i] = sorted(list(res[i]))\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        to = defaultdict(set)\n",
    "        fr =  defaultdict(set)\n",
    "        for i in edges:\n",
    "            to[i[0]].add(i[1])\n",
    "            fr[i[1]].add(i[0])\n",
    "        res = [set()for i in range(n)]\n",
    "        queue =deque([])\n",
    "        for i in range(n):\n",
    "            if not fr[i]:\n",
    "                queue.append(i)\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for i in to[node]:\n",
    "                res[i].add(node)\n",
    "                res[i]|=res[node]\n",
    "                fr[i].remove(node)\n",
    "                if not fr[i]:\n",
    "                    queue.append(i)\n",
    "        for i in range(len(res)):\n",
    "            res[i] = sorted(list(res[i]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        anc = [set() for _ in range(n)] #存储的辅助数组\n",
    "        e = [ [] for _ in range(n)]\n",
    "        indeg = [0] * n\n",
    "\n",
    "        for u,v in edges:\n",
    "            e[u].append(v)\n",
    "            indeg[v] += 1 #入度\n",
    "        \n",
    "        # BFS\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            for v in e[u]:\n",
    "                anc[v].add(u)\n",
    "                anc[v].update(anc[u])\n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    q.append(v)\n",
    "        \n",
    "        res = [sorted(anc[i]) for i in range(n)]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        ret = [set() for _ in range(n)]\n",
    "        inDegree = [0] * n\n",
    "        for u, v in edges:\n",
    "            graph[u].append(v)\n",
    "            inDegree[v] += 1\n",
    "        \n",
    "        que = deque(u for u, d in enumerate(inDegree) if d == 0)\n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "            for v in graph[u]:\n",
    "                ret[v].add(u)\n",
    "                ret[v].update(ret[u])\n",
    "                inDegree[v] -= 1\n",
    "                if inDegree[v] == 0:\n",
    "                    que.append(v)\n",
    "        return [sorted(ret[i]) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        parent_list = [0] * n\n",
    "        for index in range(n):\n",
    "            parent_list[index] = set()\n",
    "        queue_deque = collections.deque()\n",
    "        in_degree_set = set()\n",
    "        adjacent_list = [0] * n\n",
    "        for index in range(n):\n",
    "            adjacent_list[index] = list()\n",
    "\n",
    "        for edge in edges:\n",
    "            adjacent_list[edge[0]].append(edge[1])\n",
    "            in_degree_set.add(edge[1])\n",
    "        for integer in range(n):\n",
    "            if integer not in in_degree_set:\n",
    "                queue_deque.append(integer)\n",
    "        while len(queue_deque):\n",
    "            pop_length = len(queue_deque)\n",
    "            queue_deque_set = set()\n",
    "            while pop_length:\n",
    "                integer = queue_deque.popleft()\n",
    "                pop_length -= 1\n",
    "                for adjacent_integer in adjacent_list[integer]:\n",
    "                    parent_list[adjacent_integer].add(integer)\n",
    "                    for element in parent_list[integer]:\n",
    "                        parent_list[adjacent_integer].add(element)\n",
    "                    if adjacent_integer not in queue_deque_set:\n",
    "                        queue_deque.append(adjacent_integer)\n",
    "                        queue_deque_set.add(adjacent_integer)\n",
    "        for index in range(n):\n",
    "            parent_list[index] = list(parent_list[index])\n",
    "            parent_list[index].sort()\n",
    "        return parent_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        d = defaultdict(lambda: set())\n",
    "        In = [0] * n\n",
    "        e = [[] for i in range(n)]\n",
    "        for i,j in edges:\n",
    "            e[i].append(j)\n",
    "            In[j] += 1\n",
    "        for i in range(n):\n",
    "            d[i].add(i)\n",
    "        q = deque([])\n",
    "        for i,j in enumerate(In):\n",
    "            if not j:\n",
    "                q.append(i)\n",
    "        ans = [[] for i in range(n)]\n",
    "        while q:\n",
    "            t = q.popleft()\n",
    "            ans[t] = [i for i in d[t] if i != t]\n",
    "            for i in e[t]:\n",
    "                In[i] -= 1\n",
    "                d[i] |= d[t]\n",
    "                if not In[i]:\n",
    "                    q.append(i)\n",
    "        for i in range(len(ans)):\n",
    "            ans[i] = sorted(ans[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        anc = [set() for _ in range(n)]\n",
    "        e = [[] for _ in range(n)] ##邻接表\n",
    "        indge = [0] * n #入度值\n",
    "        \n",
    "        for (u,v) in edges:\n",
    "            e[u].append(v)\n",
    "            indge[v] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if indge[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            for v in e[u]:\n",
    "                anc[v].add(u)\n",
    "                anc[v].update(anc[u])\n",
    "                indge[v] -= 1\n",
    "                if indge[v] == 0:\n",
    "                    q.append(v)\n",
    "        \n",
    "        res = [sorted(anc[i]) for i in range(n)]\n",
    "    \n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "\n",
    "        indegree = defaultdict(int)\n",
    "        relation = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            indegree[y] += 1\n",
    "            relation[x].append(y)\n",
    "        q = [x for x in range(n) if x not in indegree]\n",
    "        res = defaultdict(set)\n",
    "        while q:\n",
    "            v = q.pop(0)\n",
    "            for i in relation.get(v, []):\n",
    "                res[i].add(v)\n",
    "                res[i].update(res[v])\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "        return [sorted(list(res[x])) if x in res else []for x in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        self.edges = edges\n",
    "        self.anc = [set() for _ in range(n)]\n",
    "        self.fa = [[] for _ in range(n)]\n",
    "        so = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            so[x].append(y)\n",
    "            self.fa[y].append(x)\n",
    "        for c, nn in enumerate(so):\n",
    "            if not nn:\n",
    "                self.findFa(c)\n",
    "        return [sorted(ss) for ss in self.anc]\n",
    "\n",
    "    def findFa(self, node):\n",
    "        if not self.anc[node]:\n",
    "            children = self.fa[node]\n",
    "            for c in children:\n",
    "            \t\tself.anc[node].update( self.findFa(c))\n",
    "        return self.anc[node] | {node}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        self.edges = edges\n",
    "        self.anc = [set() for _ in range(n)]\n",
    "        self.fa = [[] for _ in range(n)]\n",
    "        so = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            so[x].append(y)\n",
    "            self.fa[y].append(x)\n",
    "        for c, nn in enumerate(so):\n",
    "            if not nn:\n",
    "                self.findFa(c)\n",
    "        return [sorted(ss) for ss in self.anc]\n",
    "\n",
    "    def findFa(self, node):\n",
    "        if not self.anc[node]:\n",
    "            children = self.fa[node]\n",
    "            temp = set()\n",
    "            for c in children:\n",
    "                temp |= self.findFa(c)\n",
    "            self.anc[node] = temp\n",
    "        return self.anc[node] | {node}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class node:\n",
    "    def __init__(self, id):\n",
    "        self.par = []\n",
    "        self.id = id\n",
    "        self.all_par = None\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def getallpar(self, node):\n",
    "        node.all_par = set(node.par)\n",
    "        for i in node.par:\n",
    "            if i.all_par != None:\n",
    "                pass\n",
    "            else:\n",
    "                self.getallpar(i)\n",
    "            node.all_par = node.all_par | i.all_par\n",
    "        return node.all_par\n",
    "\n",
    "\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        node_lst = []\n",
    "        self.node_lst = node_lst\n",
    "        for i in range(n):\n",
    "            node_lst.append(node(i))\n",
    "        \n",
    "        for edge in edges:\n",
    "            par, i = edge\n",
    "            node_lst[i].par.append(node_lst[par])\n",
    "        \n",
    "        # self.output = [None for i in range(n)]\n",
    "        output = []\n",
    "        for i, v in enumerate(node_lst):\n",
    "            if v.all_par != None:\n",
    "                pass\n",
    "            else:\n",
    "                self.getallpar(node_lst[i])\n",
    "            t = [i.id for i in v.all_par]\n",
    "            t.sort()\n",
    "            output.append(t)\n",
    "\n",
    "        return output\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        \"\"\"带祖先表的拓扑排序\"\"\"\n",
    "        # 求拓扑排序的问题，感觉是 入度表+BFS 的方式更好理解一些\n",
    "        indegrees = [0] * n    # 入度\n",
    "        prerequisites = edges\n",
    "        # 建图\n",
    "        edges = collections.defaultdict(list)\n",
    "        for p in prerequisites:\n",
    "            indegrees[p[1]] += 1\n",
    "            edges[p[0]].append(p[1])\n",
    "        # print(indegrees)\n",
    "        # print(edges)\n",
    "\n",
    "        # 队列初始化，入度为0的节点进入队列\n",
    "        queue = collections.deque()\n",
    "        for i, indegree in enumerate(indegrees):\n",
    "            if indegree == 0:\n",
    "                queue.append(i)\n",
    "        # print(queue)\n",
    "\n",
    "        # 初始化祖先表\n",
    "        father = [set() for _ in range(n)]\n",
    "\n",
    "        res = []\n",
    "\n",
    "        visited = 0     # 看是否能拓扑排序完\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            visited += 1\n",
    "            res.append(cur)\n",
    "            # 遍历下一层节点\n",
    "            for nxt in edges[cur]:\n",
    "                father[nxt].add(cur)\n",
    "                father[nxt].update(father[cur])\n",
    "                indegrees[nxt] -=1\n",
    "                if indegrees[nxt] == 0:\n",
    "                    queue.append(nxt)\n",
    "        print(res)\n",
    "        print(father)\n",
    "\n",
    "        return [sorted(list(f)) for f in father]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        ans = [set() for _ in range(n)]\n",
    "        g = defaultdict(list)\n",
    "        degree = [0 for i in range(n)]\n",
    "        for s,e in edges:\n",
    "            g[s].append(e)\n",
    "            degree[e] += 1\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if degree[i] == 0:\n",
    "                q.append(i)\n",
    "        while q:\n",
    "            tmp = q.pop(0)\n",
    "            for node in g[tmp]:\n",
    "                for j in ans[tmp]:\n",
    "                    ans[node].add(j)\n",
    "                ans[node].add(tmp)\n",
    "                degree[node] -= 1\n",
    "                if degree[node] == 0:\n",
    "                    q.append(node)\n",
    "        return [sorted(i) for i in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        childrenMap = {}\n",
    "        parentsMap = {}\n",
    "        for edge in edges:\n",
    "            child, parent = edge[1], edge[0]\n",
    "            if child not in parentsMap:\n",
    "                parentsMap[child] = set()\n",
    "            parentsMap[child].add(parent)\n",
    "            \n",
    "            if parent not in childrenMap:\n",
    "                childrenMap[parent] = set()\n",
    "            childrenMap[parent].add(child)\n",
    "                \n",
    "        queue = []\n",
    "        for i in range(n):\n",
    "            if i not in parentsMap:\n",
    "                queue.append(i)\n",
    "        \n",
    "        res = [set() for _ in range(n)]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node not in childrenMap:\n",
    "                continue\n",
    "            for child in childrenMap[node]:\n",
    "                res[child].add(node)\n",
    "                for temp in res[node]:\n",
    "                    res[child].add(temp)\n",
    "                # res[child] += [node] + res[node]\n",
    "                parentsMap[child].remove(node)\n",
    "                if len(parentsMap[child]) == 0:\n",
    "                    queue.append(child)\n",
    "        \n",
    "        res = [sorted(list(ele)) for ele in res]\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        # method3\n",
    "        res_set = [set() for _ in range(n)]\n",
    "        nexts = [[] for _ in range(n)]\n",
    "        in_deg = [0] * n\n",
    "\n",
    "        for u, v in edges:\n",
    "            nexts[u].append(v)\n",
    "            in_deg[v] += 1\n",
    "        \n",
    "        d = collections.deque()\n",
    "        for i in range(n):\n",
    "            if in_deg[i] == 0:\n",
    "                d.append(i)\n",
    "        \n",
    "        while d:\n",
    "            u = d.popleft()\n",
    "            for v in nexts[u]:\n",
    "                res_set[v].add(u)\n",
    "                for j in res_set[u]:\n",
    "                    res_set[v].add(j)\n",
    "                in_deg[v] -= 1\n",
    "                if in_deg[v] == 0:\n",
    "                    d.append(v)\n",
    "        \n",
    "        return [sorted(res_set[i]) for i in range(n)]\n",
    "\n",
    "\n",
    "\n",
    "        # # method2\n",
    "        # nexts = [[] for _ in range(n)]\n",
    "        # for first, second in edges:\n",
    "        #     nexts[first].append(second)\n",
    "        \n",
    "        # answer = [[] for _ in range(n)]\n",
    "        # s = set()\n",
    "        # st = []\n",
    "        # for i in range(n):\n",
    "        #     s.clear()\n",
    "        #     s.add(i)\n",
    "\n",
    "        #     st.append(i)\n",
    " \n",
    "        #     while st:\n",
    "        #         first = st.pop()\n",
    "        #         for second in nexts[first]:\n",
    "        #             if second not in s:\n",
    "        #                 answer[second].append(i)\n",
    "        #                 s.add(second)\n",
    "        #                 st.append(second)\n",
    "        # return answer\n",
    "\n",
    "\n",
    "        # # method1\n",
    "        # nexts = [[] for _ in range(n)]\n",
    "        # for first, second in edges:\n",
    "        #     nexts[first].append(second)\n",
    "        \n",
    "        # answer = [[] for _ in range(n)]\n",
    "        # s = set()\n",
    "        # d = collections.deque()\n",
    "        # for i in range(n):\n",
    "        #     s.clear()\n",
    "        #     s.add(i)\n",
    "\n",
    "        #     d.append(i)\n",
    "        #     # d.clear()\n",
    "        #     # for v in nexts[i]:\n",
    "        #     #     answer[v].append(i)\n",
    "        #     #     s.add(v)\n",
    "        #     #     d.append(v)\n",
    "        #     while d:\n",
    "        #         first = d.popleft()\n",
    "        #         for second in nexts[first]:\n",
    "        #             if second not in s:\n",
    "        #                 answer[second].append(i)\n",
    "        #                 s.add(second)\n",
    "        #                 d.append(second)\n",
    "        # return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        # 当一个节点没有祖先的时候，它的祖先也可以看作是它自己\n",
    "        # 当BFS搜索到一个节点的时候，当它的祖先都已经找到的时候这个点才能继续向下计算\n",
    "        zuxian = [set() for _ in range(n)]\n",
    "        innode = [0]*n\n",
    "        Map = {}\n",
    "        for st,end in edges:\n",
    "            if st in Map:\n",
    "                Map[st].append(end)\n",
    "            else:\n",
    "                Map[st] = [end]\n",
    "            innode[end] += 1\n",
    "        \n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            if innode[i] == 0:\n",
    "                q.append(i)\n",
    "        \n",
    "        # 有向无环图就不用visited数组来避免重复访问节点的问题了\n",
    "        # 在收集的时候没有去重\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if node in Map:\n",
    "                for nxt in Map[node]:\n",
    "                    innode[nxt] -= 1\n",
    "                    zuxian[nxt].add(node)\n",
    "                    for zu in zuxian[node]:\n",
    "                        zuxian[nxt].add(zu)\n",
    "                    if innode[nxt] == 0:\n",
    "                        q.append(nxt)\n",
    "        zuxian = [sorted(list(i)) for i in zuxian]\n",
    "        return zuxian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        vis = [0] * n \n",
    "        g = collections.defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[v].append(u)\n",
    "        ans = [{} for _ in range(n)]\n",
    "        def dfs(u):\n",
    "            nonlocal ans \n",
    "            se = set()\n",
    "            for v in g[u]:\n",
    "                se.add(v)\n",
    "                if vis[v]:\n",
    "                    se |= ans[v]\n",
    "                    continue\n",
    "                se |= dfs(v)\n",
    "            ans[u] = se\n",
    "            vis[u] = 1\n",
    "            return se\n",
    "        for i in range(n):\n",
    "            if vis[i]:\n",
    "                continue\n",
    "            dfs(i)\n",
    "        ret = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            ret[i] = list(ans[i])\n",
    "            ret[i].sort()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # reverse edge + DFS\n",
    "    def makeGraph(self, n, edges):\n",
    "        graph = defaultdict(list)\n",
    "        indeg = defaultdict(int)\n",
    "        for src, dest in edges:\n",
    "            graph[dest].append(src)\n",
    "            indeg[src] += 1\n",
    "        return graph, indeg\n",
    "\n",
    "    def dfs(self, node, graph, sets, visited):\n",
    "        if visited[node]:\n",
    "            return\n",
    "        visited[node] = True\n",
    "        for nb in graph[node]:\n",
    "            self.dfs(nb, graph, sets, visited)\n",
    "            sets[node].add(nb)\n",
    "            for ans in sets[nb]:\n",
    "                sets[node].add(ans)\n",
    "        return\n",
    "    \n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        graph, indeg = self.makeGraph(n, edges)\n",
    "        sets = [set() for _ in range(n)]\n",
    "        visited = [False] * n\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if indeg[i] == 0:\n",
    "                self.dfs(i, graph, sets, visited)\n",
    "        for i in range(n):\n",
    "            nbs = list(sets[i])\n",
    "            nbs.sort()\n",
    "            res.append(nbs)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        def find_parent(node):\n",
    "            if has_get_parent[node]:\n",
    "                return\n",
    "            for v in dct[node].copy():\n",
    "                if has_get_parent[v]:\n",
    "                    dct[node].update(dct[v])\n",
    "                else:\n",
    "                    find_parent(v)\n",
    "                    has_get_parent[v] = True\n",
    "                    dct[node].update(dct[v])\n",
    "\n",
    "        dct, has_get_parent = {}, {}\n",
    "        for i in range(n):\n",
    "            dct[i] = set()\n",
    "            has_get_parent[i] = True\n",
    "        # 初始化一级祖先\n",
    "        for edge in edges:\n",
    "            has_get_parent[edge[1]] = False\n",
    "            dct[edge[1]].add(edge[0])\n",
    "        # 递归找所有祖先\n",
    "        for k, v in list(dct.items()):\n",
    "            find_parent(k)\n",
    "            has_get_parent[k] = True\n",
    "\n",
    "        return [sorted(v) for v in dct.values()]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = defaultdict(list)\n",
    "        inc = [0 for _ in range(n)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            m[x].append(y)\n",
    "            inc[y] += 1\n",
    "        que = [i for i in range(n) if inc[i]==0]\n",
    "        f = [set() for _ in range(n)]\n",
    "        print(que)\n",
    "        while que:\n",
    "            q2 = []\n",
    "            for x in que:\n",
    "                for y in m[x]:\n",
    "                    f[y].add(x)\n",
    "                    f[y].update(f[x])\n",
    "                    inc[y] -= 1\n",
    "                    if inc[y]==0:\n",
    "                        q2.append(y)\n",
    "            que = q2\n",
    "        print(f)\n",
    "        # ans = [sorted(list(fi)) for fi in f]\n",
    "        ans = [sorted(fi) for fi in f]\n",
    "        print(ans)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        m = defaultdict(list)\n",
    "        inc = [0 for _ in range(n)]\n",
    "        for e in edges:\n",
    "            x, y = e[0], e[1]\n",
    "            m[x].append(y)\n",
    "            inc[y] += 1\n",
    "        que = [i for i in range(n) if inc[i]==0]\n",
    "        f = [set() for _ in range(n)]\n",
    "        print(que)\n",
    "        while que:\n",
    "            q2 = []\n",
    "            for x in que:\n",
    "                for y in m[x]:\n",
    "                    f[y].add(x)\n",
    "                    f[y].update(f[x])\n",
    "                    inc[y] -= 1\n",
    "                    if inc[y]==0:\n",
    "                        q2.append(y)\n",
    "            que = q2\n",
    "        print(f)\n",
    "        ans = [sorted(list(fi)) for fi in f]\n",
    "        print(ans)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        ret = [[] for _ in range(n)]\n",
    "        mk = [defaultdict(lambda:0) for _ in range(n)] \n",
    "        inDeg, outDeg = defaultdict(lambda:0), defaultdict(lambda:[])\n",
    "        for a, b in edges:\n",
    "            outDeg[a].append(b)\n",
    "            inDeg[b] += 1\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if 0 == inDeg[i]:\n",
    "                q.append(i)\n",
    "        while len(q) > 0:\n",
    "            a = q.pop(0)\n",
    "            for c in outDeg[a]:\n",
    "                inDeg[c] -= 1\n",
    "                for p in ret[a]:\n",
    "                    if 0 == mk[c][p]:\n",
    "                        mk[c][p] = 1\n",
    "                        ret[c].append(p)\n",
    "                mk[c][a] = 1\n",
    "                ret[c].append(a)\n",
    "                if 0 == inDeg[c]:\n",
    "                    q.append(c)\n",
    "        for r in ret:\n",
    "            r.sort()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        ret = [[] for _ in range(n)]\n",
    "        mk = [defaultdict(lambda:0) for _ in range(n)] \n",
    "        inDeg, outDeg = defaultdict(lambda:0), defaultdict(lambda:[])\n",
    "        for a, b in edges:\n",
    "            outDeg[a].append(b)\n",
    "            inDeg[b] += 1\n",
    "        q = []\n",
    "        for i in range(n):\n",
    "            if 0 == inDeg[i]:\n",
    "                q.append(i)\n",
    "        while len(q) > 0:\n",
    "            a = q.pop(0)\n",
    "            for c in outDeg[a]:\n",
    "                inDeg[c] -= 1\n",
    "                for p in ret[a]:\n",
    "                    if 0 == mk[c][p]:\n",
    "                        mk[c][p] = 1\n",
    "                        ret[c].append(p)\n",
    "                mk[c][a] = 1\n",
    "                ret[c].append(a)\n",
    "                if 0 == inDeg[c]:\n",
    "                    q.append(c)\n",
    "        for r in ret:\n",
    "            r.sort()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        adjList, res = [set() for _ in range(n)], [[] for _ in range(n)]\n",
    "        for x in edges:\n",
    "            adjList[x[0]].add(x[1])\n",
    "        for i in range(n):\n",
    "            already = adjList[i]\n",
    "            stack = list(adjList[i])\n",
    "            while stack:\n",
    "                pres = stack.pop()\n",
    "                res[pres].append(i)\n",
    "                for x in adjList[pres]:\n",
    "                    if x not in already:\n",
    "                        already.add(x)\n",
    "                        stack.append(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Graph: \n",
    "    def __init__(self,vertices): \n",
    "        self.graph = defaultdict(list) \n",
    "        self.V = vertices\n",
    "  \n",
    "    def addEdge(self,u,v): \n",
    "        self.graph[u].append(v) \n",
    "  \n",
    "    def topologicalSortUtil(self,v,visited,stack): \n",
    "  \n",
    "        visited[v] = True\n",
    "  \n",
    "        for i in self.graph[v]: \n",
    "            if visited[i] == False: \n",
    "                self.topologicalSortUtil(i,visited,stack) \n",
    "  \n",
    "        stack.insert(0,v) \n",
    "  \n",
    "    def topologicalSort(self): \n",
    "        visited = [False]*self.V \n",
    "        stack =[] \n",
    "  \n",
    "        for i in range(self.V): \n",
    "            if visited[i] == False: \n",
    "                self.topologicalSortUtil(i,visited,stack)\n",
    "        return stack\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        father = defaultdict(set)\n",
    "        g = Graph(n)\n",
    "        for _from,_to in edges:\n",
    "            g.addEdge(_from,_to)\n",
    "            father[_to].add(_from)\n",
    "        res = defaultdict(list)\n",
    "        num = g.topologicalSort()\n",
    "        for i in num:\n",
    "            tmp = father[i].copy()\n",
    "            for j in tmp:\n",
    "                father[i] |= father[j]\n",
    "           \n",
    "            res[i]=sorted(list(father[i]))\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            ans.append(res[i])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges):\n",
    "\n",
    "        def DFS(i):\n",
    "            if i in dfs:\n",
    "                return dfs[i]\n",
    "            a={i}\n",
    "            for nextdis in adj[i]:\n",
    "                a=a|DFS(nextdis)\n",
    "            dfs[i]=a\n",
    "            return a\n",
    "\n",
    "        dfs=dict()\n",
    "\n",
    "        indegree=[0 for _ in range(n)]\n",
    "        adj=[[] for _ in range(n)]\n",
    "        for f,t in edges:\n",
    "            adj[t].append(f)\n",
    "            indegree[f]+=1\n",
    "\n",
    "        for i in range(n):\n",
    "            if indegree[i]==0:DFS(i)\n",
    "\n",
    "        ans = [dfs[i] for i in range(n)]\n",
    "        for i in range(n):\n",
    "            ans[i].remove(i)\n",
    "            ans[i]=list(ans[i])\n",
    "            ans[i].sort()\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Set\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        graph = [[] for i in range(n)]\n",
    "        for e in edges:\n",
    "            graph[e[1]].append(e[0])\n",
    "        computed = [0 for i in range(n)]\n",
    "        fathers = [set() for i in range(n)]\n",
    "        def dfs(cur: int) -> Set[int]:\n",
    "            if computed[cur]: return fathers[cur]\n",
    "            fc = set()\n",
    "            for v in graph[cur]:\n",
    "                fc.add(v)\n",
    "                fc = fc.union(dfs(v))\n",
    "            computed[cur] = 1\n",
    "            fathers[cur] = fc\n",
    "            return fc\n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "        return [sorted(list(fathers[i])) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        # get indegree\n",
    "        indegree = [0 for _ in range(n)]\n",
    "\n",
    "        # get new graph\n",
    "        new_graph = [[] for _ in range(n)]\n",
    "\n",
    "        for e in edges:\n",
    "            indegree[e[1]] += 1\n",
    "            new_graph[e[0]].append(e[1])\n",
    "\n",
    "        print(indegree)\n",
    "        print(new_graph)\n",
    "\n",
    "        # define a Queue\n",
    "        q = deque()\n",
    "\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                q.append(i)\n",
    "\n",
    "        res = [set() for _ in range(n)]\n",
    "\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    " \n",
    "            for i in new_graph[cur]:\n",
    "                indegree[i] -= 1\n",
    "                if indegree[i] == 0:\n",
    "                    q.append(i)\n",
    "                for j in res[cur]:\n",
    "                    res[i].add(j)\n",
    "                res[i].add(cur)\n",
    "\n",
    "        print([list(_) for _ in res])\n",
    "        return [sorted(list(_)) for _ in res]\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "#         res = [set() for i in range(n)]\n",
    "#         degree = [0 for i in range(n)]#入度\n",
    "#         t = [[] for i in range(n)]#子节点列表\n",
    "#         for f, tt in edges:\n",
    "#             degree[tt] += 1#入度+1\n",
    "#             t[f].append(tt)#加入子节点列表\n",
    "#         deq = []\n",
    "#         for i in range(n):\n",
    "#             if degree[i] == 0:#将入度为0的入列\n",
    "#                 deq.append(i)\n",
    "#         while deq:\n",
    "#             i = deq.pop(0)\n",
    "#             for j in t[i]:#遍历父节点的子节点列表\n",
    "#                 for k in res[i]:\n",
    "#                     res[j].add(k)#父节点的祖先节点一定是子节点的祖先节点\n",
    "#                 res[j].add(i)#加入父节点\n",
    "#                 degree[j] -= 1#入度-1\n",
    "#                 if degree[j] == 0:#当入度为0代表父节点已遍历完,子节点加入队列\n",
    "#                     deq.append(j)\n",
    "#         return [sorted(i) for i in res]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        res = [[] for i in range(n)]\n",
    "        parents = collections.defaultdict(list)\n",
    "        g = collections.defaultdict(list)\n",
    "\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            parents[b].append(a)\n",
    "\n",
    "        @functools.cache\n",
    "        def dfs(node):\n",
    "            ancestors = set()\n",
    "            for p in parents[node]:\n",
    "                ancestors.update(dfs(p))\n",
    "            res[node] = sorted(ancestors)\n",
    "            return ancestors.union({node})\n",
    "        \n",
    "        for i in range(n):\n",
    "            if not g[i]:\n",
    "                dfs(i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:              \n",
    "        inDegree, outDegree, parent = {u:0 for u in range(n)}, {u:[] for u in range(n)}, [set() for _ in range(n)]\n",
    "        for u, v in edges:           \n",
    "            outDegree[u].append(v)\n",
    "            inDegree[v] += 1\n",
    "           \n",
    "        answer = [[]for _ in range(n)]   \n",
    "     \n",
    "        while len(inDegree) != 0:\n",
    "            nodes = []\n",
    "            for u, deg_ in inDegree.items():\n",
    "                if deg_ == 0:                    \n",
    "                    nodes.append(u)\n",
    "                    answer[u] = list(parent[u])\n",
    "                       \n",
    "            for u in nodes:                        \n",
    "                for v in outDegree[u]:  \n",
    "                    parent[v].add(u)                                      \n",
    "                    for i in parent[u]:\n",
    "                        parent[v].add(i)                                        \n",
    "                    inDegree[v] -= 1\n",
    "                del inDegree[u]\n",
    "\n",
    "            # n -= len(nodes)\n",
    "\n",
    "        for a in answer:\n",
    "            a.sort()\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        d = defaultdict(list)\n",
    "        for u, v in edges: d[v].append(u)\n",
    "        @cache\n",
    "        def f(v): return reduce(lambda r, u: r | f(u) , d[v], set(d[v]))\n",
    "        return [sorted(f(v)) for v in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        # 集合列表：存储每个节点的祖先\n",
    "        ancestor = [set() for _ in range(n)]\n",
    "\n",
    "        # 构建反邻接表  求节点祖先变成求后代\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[b].append(a)\n",
    "        \n",
    "        visited = [False] * n \n",
    "        \n",
    "        def dfs(node: int):\n",
    "            \"\"\"搜索当前节点的后代\n",
    "            \"\"\"\n",
    "            if visited[node]:\n",
    "                return \n",
    "            \n",
    "            visited[node] = True \n",
    "\n",
    "            for neighbor in g[node]:\n",
    "                dfs(neighbor)\n",
    "                ancestor[node].add(neighbor)\n",
    "                ancestor[node].update(ancestor[neighbor])\n",
    "            \n",
    "        for i in range(n):\n",
    "            dfs(i)\n",
    "\n",
    "        return [sorted(ancestor[i]) for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        fa = [[0] * n for _ in range(n)]\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            indegree[b] += 1\n",
    "        Q = []\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                Q.append(i)\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.pop(0)\n",
    "            for v in g[u]:\n",
    "                fa[v][u] = 1 \n",
    "                for i in range(n):\n",
    "                    if fa[u][i]:\n",
    "                        fa[v][i] = 1\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    Q.append(v)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            for j in range(n):\n",
    "                if fa[i][j]:\n",
    "                    t.append(j)\n",
    "            ans.append(t)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        fa = [[0] * n for _ in range(n)]\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        indegree = defaultdict(int)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            indegree[b] += 1\n",
    "        Q = deque()\n",
    "        for i in range(n):\n",
    "            if indegree[i] == 0:\n",
    "                Q.append(i)\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            for v in g[u]:\n",
    "                fa[v][u] = 1 \n",
    "                for i in range(n):\n",
    "                    if fa[u][i]:\n",
    "                        fa[v][i] = 1\n",
    "                indegree[v] -= 1\n",
    "                if indegree[v] == 0:\n",
    "                    Q.append(v)\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            t = []\n",
    "            for j in range(n):\n",
    "                if fa[i][j]:\n",
    "                    t.append(j)\n",
    "            ans.append(t)\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        adjList = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            adjList[v].append(u)\n",
    "\n",
    "        @cache\n",
    "        def dfs(now):\n",
    "            return reduce(\n",
    "                lambda m, n: m | n,\n",
    "                map(dfs, adjList[now]),\n",
    "                set([now])\n",
    "            )\n",
    "        \n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            x = sorted(dfs(i))\n",
    "            x.remove(i)\n",
    "            ans.append(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        d = defaultdict(list)\n",
    "        for u, v in edges: d[v].append(u)\n",
    "        @cache\n",
    "        def f(v): return reduce(ior, [f(u) for u in d[v]], set(d[v]))\n",
    "        return [sorted(f(v)) for v in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        ans, flag = [set() for _ in range(n)], True\n",
    "        for i, j in edges:\n",
    "            ans[j].add(i)\n",
    "        while flag:\n",
    "            #print(ans)\n",
    "            flag = False\n",
    "            for i, a in enumerate(ans):\n",
    "                for j in list(a):\n",
    "                    if ans[j] - ans[i]:\n",
    "                        flag = True\n",
    "                        ans[i] |= ans[j]\n",
    "        return [sorted(a) for a in ans]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getAncestors(self, n: int, edges: List[List[int]]) -> List[List[int]]:\n",
    "        graph = defaultdict(list)\n",
    "        indeg = [0]*n\n",
    "        for a, b in edges:\n",
    "            graph[a].append(b)\n",
    "            indeg[b] += 1\n",
    "        \n",
    "        ans = [set() for _ in range(n)]\n",
    "        \n",
    "        \n",
    "        \n",
    "        def dfs(i, x):\n",
    "            colors[i] = 1\n",
    "            for j in graph[i]:\n",
    "                ans[j].add(x)\n",
    "                if colors[j] == 0:\n",
    "                    dfs(j, x)\n",
    "        for i in range(n):\n",
    "            colors = [0]*n\n",
    "            dfs(i, i)\n",
    "        return [sorted(x) for x in ans]\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def getAncestors(self, n, edges):\n",
    "        ans, flag = [set() for _ in range(n)], True\n",
    "        for i, j in edges: ans[j].add(i)\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for i, a in enumerate(ans):\n",
    "                for j in list(a):\n",
    "                    if ans[j] - ans[i]:\n",
    "                        flag = True\n",
    "                        ans[i] |= ans[j]\n",
    "        return [sorted(a) for a in ans]        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
